package algorithm.leetcode.medium;

/*
 在未排序的数组中找到第 k 个最大的元素。请注意，
 你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 */


/**
 * @author jack.wu
 * @version 1.0
 * @date 2020/12/17
 */
public class Question215 {

    public static void main(String[] args) {
        int[] nums = {3,2,3,1,2,4,5,5,6};
        Question215 question = new Question215();
        int kthLargest = question.findKthLargest(nums, 4);
        System.out.println(kthLargest);
    }

    public int findKthLargest(int[] nums, int k) {
        quickSort(nums);
        return nums[nums.length - k];
    }

    private void quickSort(int[] nums) {
        helper(nums, 0, nums.length - 1);
    }

    private void helper(int[] nums, int left, int right) {
        if (left > right) {
            return;
        }
        int pivot = nums[left];
        int l = left;
        int r = right;
        int temp;
        while (l < r) {
            while (l < r && nums[r] >= pivot) {
                r--;
            }
            while (l < r && nums[l] <= pivot) {
                l++;
            }
            if (l < r) {
                temp = nums[l];
                nums[l] = nums[r];
                nums[r] = temp;
            }
        }
        nums[left] = nums[l];
        nums[l] = pivot;
        helper(nums, left, l - 1);
        helper(nums, l + 1, right);
    }
}
